package leetcode_500;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 *@author 周杨
 *NextGreaterElementI_496 找出Nums2中每一个比它大的近的元素  nums2里包含了nums1的元素 且不重复
 *describe:AC 84% 用栈和hash
 *2018年9月4日 下午5:43:04
 */
public class NextGreaterElementI_496 {
	 public int[] nextGreaterElement(int[] nums1, int[] nums2) {
	       Map<Integer,Integer> hash=new HashMap<Integer,Integer>();
	       Stack<Integer> stack=new Stack<Integer>();
	       for(int num:nums2) {
	    	   while(!stack.isEmpty()&&num>stack.peek()) {
	    		   hash.put(stack.pop(), num);
	    	   }
	    	   stack.push(num);
	       }
	       for(int i=0;i<nums1.length;++i) {
	    	   nums1[i]=hash.getOrDefault(nums1[i], -1);
	       }
	       return nums1;
	 }
}
